// 多项式相加（链式存储）
#include <stdio.h>
#include <stdlib.h>

// 定义结构体
typedef struct PNode
{
    float coef;         // 系数
    int expn;           // 指数
    struct PNode *next; // 指向下一个节点的指针
} PNode, *Polynomial;   // Polynomial 是指向 PNode 的指针

// 根据输入的项依次插入到链表中
// void CreatePolyn(Polynomial &P, int n)//Polynomial &P不合法
/*也可以这样搞
int main()
{
    // 定义头节点p
    Polynomial P = (PNode *)malloc(sizeof(PNode));
    P->next = NULL;

    int n;
    scanf("%d", &n);

    CreatePolyn(P, n); 
    ...
}

void CreatePolyn(Polynomial P,int n){
    PNode *s;   // 用于存储新项的指针
    PNode *q;   // q为当前节点，用于遍历节点
    PNode *pre; // pre为q的前驱节点
    ...
}
*/
void CreatePolyn(Polynomial *P,int n){//Polynomial *P是一个指向Polynomial的指针（即PNode **），可以让函数修改原始的链表头指针
    // 先建立带头结点的空链表
    *P = (PNode *)malloc(sizeof(PNode));//* 表示解引用操作符,P解引用后才是指向 PNode 的实际对象
    (*P)->next = NULL;

    // 定义几个要用到的指针
    PNode *s;   // 用于存储新项的指针
    PNode *q;   // q为当前节点，用于遍历节点
    PNode *pre; // pre为q的前驱节点

    // 根据输入的项依次插入到链表中
    for (int i = 0; i < n; i++)
    {
        s = (PNode *)malloc(sizeof(PNode));
        scanf("%f%d", &s->coef, &s->expn); // 创建一个节点

        pre = *P;     // pre初始化为头节点
        q = pre->next; // q初始化为第一个节点

        // 使用 pre 和 q 两个指针遍历链表，寻找适合插入新项的位置
        while (q && q->expn < s->expn)
        { // 当q不为空 且 新项指数仍大于当前指数，则继续遍历，直到找到插入位置
            pre = q;
            q = pre->next; // 移向下一个节点
        }

        if (q && q->expn == s->expn) {  // 如果指数相同，累加系数
            q->coef += s->coef;
            free(s);  // 释放新节点内存
        } else {
            s->next = q; // 找到位置后插入
            pre->next = s;
        }
        // 进行下一次项的插入
    }
}

// 打印链表
void PrintPloyn(Polynomial P)
{
    PNode *q = P->next; // 指向多项式第一个节点
    while (q)
    {
        printf("%.1fx^%d", q->coef, q->expn);
        q = q->next;
        if (q)
        {
            printf("+");
        }
    }
    printf("\n");
}

int main()
{
    Polynomial P; // 定义头节点p

    int n;
    scanf("%d", &n);

    CreatePolyn(&P, n); // 创建链表

    printf("多项式="); // 打印链表
    PrintPloyn(P);

    // 释放链表内存
    PNode *current = P;
    PNode *nextnode;
    while (current)
    {
        nextnode = current->next;
        free(current);
        current = nextnode;
    }

    return 0;
}